package _25_复杂链表的复制;
/*
题目描述
输入一个复杂链表
（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），
返回结果为复制后复杂链表的head。
（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）

 */

import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;

/**
 * 思路：
 * 将每一个节点复制到原来节点的后面
 * 第二次将random指向原来的后面
 * 再将链表覆盖回去
 */
class RandomListNode {
    int label;
    RandomListNode next = null;
    RandomListNode random = null;

    RandomListNode(int label) {
        this.label = label;
    }
}

public class Solution {
    public RandomListNode Clone(RandomListNode pHead) {
        if (pHead == null) return null;
        RandomListNode p = pHead;
        while (p != null) {
            RandomListNode newNode = new RandomListNode(p.label);
            newNode.next = p.next;//新节点的下一个是原节点的下一个
            p.next = newNode;//现节点的下一个是新节点

            p = newNode.next;//p为原节点的原下一个节点

        }
        p = pHead;
        //第二次循环修改随机的节点
        while (p != null) {
            if (p.random != null) {
                p.next.random = p.random.next;
            }
            p = p.next.next;
        }
        //第三次删除原来的

        RandomListNode res = pHead.next;
        p = pHead;
        while (p != null) {
            RandomListNode clone = p.next;
            RandomListNode oldNext = clone.next;
            p.next = oldNext;

            clone.next = clone.next == null ? null : oldNext.next;
            p = oldNext;

        }
        return res;
    }

    public RandomListNode Clone2(RandomListNode pHead) {
        RandomListNode p = pHead;
        HashMap<RandomListNode,RandomListNode> map = new HashMap<>();
        RandomListNode clone = new RandomListNode(-1);
        while(p!=null){
            RandomListNode newNode = new RandomListNode(p.label);
            clone.next = newNode;
            map.put(p,newNode);
            p=p.next;
            clone = clone.next;
        }

        for(Map.Entry<RandomListNode,RandomListNode> entry: map.entrySet()){
            entry.getValue().random = map.get(entry.getKey().random);
        }
        return map.get(pHead);
    }
}
